Richard Karp

概述

美国计算机科学家（1935–），1972年发表里程碑式论文《Reducibility among combinatorial problems》，通过一系列归约证明了21个经典组合问题都是 NP 完全的，极大地拓展了 NP 完全性理论的应用范围。

通过从 SAT 出发的多项式时间归约，证明了以下21个问题都是 NP 完全的：

图论问题： - 团问题（CLIQUE） - 独立集（INDEPENDENT SET） - 顶点覆盖（VERTEX COVER） - 图着色（GRAPH COLORING） - 哈密顿回路（HAMILTONIAN CIRCUIT）

逻辑问题： - 3-SAT

数论/优化问题： - 背包问题（KNAPSACK） - 子集和问题（SUBSET SUM） - 整数规划（INTEGER PROGRAMMING）

调度问题： - 作业车间调度（JOB SHOP SCHEDULING）

Karp 的工作展示了多项式归约作为工具的强大威力——一旦知道 SAT 是 NP 完全的，只需要把 SAT 归约到一个新问题，就能证明新问题也是 NP 完全的。这种"链式传递"的归约方法成为了后来 NP 完全性证明的标准范式。

今天已知有数千个问题是 NP 完全的，Karp 的21个问题是这条归约链的起点。